import java.util.*;

public class Offer38 {
    Set<String> set = new HashSet<>();

    public String[] permutation(String s) {
        if (s == null || s.isEmpty()) return null;
        char[] chars = s.toCharArray();
        boolean[] booleans = new boolean[chars.length];
        backtrack(chars, 0, booleans, "");
        String[] strings = new String[set.size()];
        int i = 0;
        for (String s1 : set) {
            strings[i++] = s1;
        }
        return strings;
    }

    public void backtrack(char[] chars, int begin, boolean[] visited, String now) {
        if (begin == chars.length) {
            set.add(now);
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                backtrack(chars, begin + 1, visited, now + chars[i]);
                visited[i] = false;
            }
        }
    }
}
